import java.util.Arrays;

public class TestDome2 {
    /**
     * 堆排序
     */
    public static void heapSort(int[] array){
        crate(array);
        int end = array.length-1;
        while(end > 0){
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            shiftDown(array,0,end);
            end--;
        }
    }
    public static void crate(int[] array){
        for (int parent = (array.length-1-1)/2; parent >= 0; parent--){
            shiftDown(array,parent,array.length);
        }
    }
    public static void shiftDown(int[] array,int parent, int len){
        int child = 2*parent+1;//确认左孩子下标
        while(child < len){
            if(child+1 < len && array[child] < array[child+1]){
                child++;
            }
            if(array[child] > array[parent]){
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                parent = child;
                child = parent*2+1;
            }else{
                break;
            }
        }
    }
    /**
     * 直接排序
     * 时间复杂度：O(N ^ 2)
     * 空间复杂度：O(1)
     * 稳定
     */
    public static void insert(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    /**
     * 选择排序
     * 时间复杂度：O(N ^ 2)
     * 空间复杂度：O(1)
     * 不稳定
     */
    public static void select(int [] array){
        for (int i = 0; i < array.length; i++) {
            for (int j = i+1; j < array.length; j++) {
                if(array[i] > array[j]){
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }
    /**
     * 时间复杂度[和增量有关系的]：O(n^1.3 - n^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定的
     *   看在比较的过程当中  是否发生了跳跃式的交换 如果发生了跳跃式的交换  那么就是不稳定的排序
     * 基本上没有考过
     * @param array
     */

    public static void shell(int [] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j+gap] = array[j];
                } else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    public static void shellSort(int [] array){
        int gap = array.length;
        while(gap > 1){
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);
    }
    public static void main(String[] args) {
        int [] array = {12,5,18,10,4,2};
       heapSort(array);
        System.out.println(Arrays.toString(array));
    }
}
